""" TopoGraph class
implements a directed acyclic graph
using incremental topographical sort
to prevent addition of cyclic links

Algorithm used is efficient for dense graphs
(m > n^(5/3), where m is edge count and n is vertex count).
Memory used is O(n^2)
Amortized performance:
O(n^(5/2)) time to add m edges
O(n^2) time to detect m cycles

Algorithm adapted from Kavitha and Mathew
"Faster Algorithms for Online Topological Ordering"
http://archive.csa.iisc.ernet.in/TR/2007/12/IISc-CSA-TR-2007-12.pdf
also see "Faster Algorithms for Incremental Topological Ordering"
by Haeupler, Kavitha, Mathew, Sen, and Tarjan
http://web.mit.edu/haeupler/www/Haeupler,Kavitha,Mathew,Sen,Tarjan_-_Faster_Algorithms_for_Incremental_Topological_Ordering.pdf

Main components of O(n^(5/2)) time:
 1) maintaining topological order
 2) checking for cycle
    - worst case cycle detection phase costs O(n^2)

so for some applications, might consider "corner case"
with repeated attempted worst case addition of cycle
- to handle this, keep track of attempted cycles via additional matrix
- incurs an extra O(n^2) space cost, with O(1) time
(Note this enhancement is not part of core method given by Kavilla / Mathew)

The adjacency matrix can use substantial amount of memory O(n^2)
(This implemention uses bitmap representations allocated as needed
to help reduce memory footprint.  A graph with 65536 vertices may use
slightly over 1 GB of memory for the 2 matrices used to store edges
and track cycles.)

Algorithm as outlined in the analysis by Haeupler et al.
(with some implementation details added)

Maintain:

 an adjacency matrix adj[n][n]
  (implementation uses dictionary of bitmaps)
  a directed edge from vertex v to vertex w
  is represented as adj[v][w] = 1

 also maintain additional matrix cyc[n][n]
  to track edges which would complete a cycle
  (this is not part of the original algorithm)

 maintain array representing topological order of vertices
  implementation actually uses 2 arrays:
  ord[] - ie, ord[v] gives unique order of vertex v
  ver[] - inverse of ord[] - supports O(1) lookup

For each edge (v, w) to be added, reinitialize and operate on:
 a set of forward vertices "fw" (can be reached from vertex w)
 a set of backward vertices "rv" (can reach vertex v)
 (implementation uses deques "fw" and "rv")

To add a link from vertex v to vertex w
1) Set adj[v][w] = 1  (tentatively - clear later if cycle found)
2) if v not already in topological order (ver[] array) then add
   (can be inserted in any arbitrary position - first empty slot is ok)
3) if w not already in topological order then add anywhere after v
4) set i = ord[w] and j = ord[v]
5) if i < j, then all done since no cycle possible
  else, if j > i ...
 1) Initialize fw to [w]
 2) Initialize rv to [v]
 3) Do an ordered two-way search
    forward from i and backward from j
    from ver[i] through ver[j]

    For each index k visited by the forward search:
      Determine if the vertex x = ver[k] is forward
        by querying adj[f][x] for each f in fw.
      If any of the queries evaluates to 1
        add x to the back of fw

    The backward search is symmetric:
      Determine if the vertex x = ver[k] is forward
        by querying adj[x][r] for each r in rv.

    (implementation uses functions "fwd()" and "rev()" in this phase)

    Stop the search when an index "m" is reached such that
     1) all vertices from ver[i] through ver[m]
       have been visited by the forward search, and
     2) all vertices from ver[m] through ver[j]
       have been visited by the backward search.
     The forward search runs until it adds a vertex to fw,
     then the backward search runs until it adds a vertex to rv,
     and so on until forward index and backward index meet at m

 At the end of the search phase, determine if (v, w) creates a cycle:
  The new edge (v, w) creates a cycle if and only if
   1) ver[m] is in both fw and rv, or
   2) there is an edge (x, y) such that x is in fw and y is in rv
   (impementation uses function "acyclic()" in this phase)

 If cycle found, clear entry in adj[v][w]
 (and set cyc[v][w] - my enhancement, not in original algorithm)

 If no cycle, continue:

 Reorder the vertices in fw and rv to restore topological order:
  1) Delete all the vertices in fw and rv from current slots in ver[]
  2) Vertices in fw must find new indices in ver[m] through ver[j]
     Vertices in rv must find new indices in ver[i] through ver[m-1]
 
     Extend the forward search to ver[mid] through ver[j]
     backward search extended symmetrically to ver[i] through ver[m-1]

     For each index k in {m,...,j}
       delete vertex f from the front of fw
       if ver[k] is empty
         place f in ver[k]
       Otherwise,
       if vertex x = ver[k] is forward
         remove x from ver[k]
         append x to fw
         place f in ver[k]
"""

from array import array
from time import time
import random
import pickle
from collections import deque

class TopoGraph:
    def __init__(self, num_vert):
        self.numv = num_vert
        self.adj = AdjacencyMatrix(self.numv)  # "edge"
        self.cyc = AdjacencyMatrix(self.numv)  # "cycle"
        self.topol = Orderer(self.numv)
        self.fw = deque()
        self.rv = deque()
        self.mid = 0

    def constraints(self, v, w):
        """Check input parameters.  Return constraint if trigerred."""
        if v < 0 or w < 0 or v >= self.numv or w >= self.numv:
            s = "v or w index out of bounds: " + str(v) + ", " + str(w)
            return s
        if v == w:
            return "edge from and to same vertex"
        if self.adj[v][w]:
            return "edge exists already"
        if self.cyc[v][w]:
            return "cycle previously attempted"
        return False  # no constraint triggered

    def insert_link(self, v, w):
        """Add edge(v, w) only if it does not complete a cycle."""
        if self.constraints(v, w): 
            return self.constraints(v, w)  # bogus input values, etc 

        self.adj[v][w] = 1  # tentatively, clear later if closes a cycle

        ord_v, ord_w = self.topol.vertex_orders(v, w)
        if ord_v > ord_w:
            if self.cycle_detected(v, w): 
                self.adj[v][w] = 0
                self.cyc[v][w] = 1
                return "cycle"
            else:
                self.update_topological_order(v, w)
        return "added"

    def cycle_detected(self, v, w):
        self.setup_order_search(v, w)
        if self.topological_acyclic(v, w):
            return False
        return True

    def topological_acyclic(self, v, w):
        """Check for edge from "fw" to "rv". If none, return False"""
        if self.fw[-1] == self.rv[-1]:  # will be last index if in both
            return False  # cycle: a vertex reachable from w reaches v
        for x in self.fw:
            for y in self.rv:
                if self.adj[x][y]:
                    return False  # cycle: reachable from w reaches v
        return True  # ok, link from v to w does not complete a cycle

    def insert_link_dfs(self, v, w):
        """Use depth-first search to detect cycle (for testing)."""
        if self.constraints(v, w):
            return self.constraints(v, w)
        if self.dfs_acyclic(v, w):
            self.adj[v][w] = 1
        else:
            self.adj[v][w] = 0
            self.cyc[v][w] = 1
            return "cycle"  # edge disallowed
        return "added"  # edge added successfully

    def dfs_acyclic(self, from_vertex, to_vertex):
        """For testing using DFS.  Return False if cycle found."""
        # print "dfs_acyclic: checking", from_vertex, to_vertex
        if self.adj[to_vertex][from_vertex]:
            return False
        lifo = self.get_edgelist(to_vertex)
        # lifo stack now contains list of edges "from" the "to_vertex"
        checked = BitArray(self.numv)
        # keep track of visited vertices in a bitmap
        while lifo:
            next_vertex = lifo.pop()
            if self.adj[next_vertex][from_vertex]:
                return False  # edge found completing a cycle
            more_vertices = self.adj[next_vertex]
            checked[next_vertex] = True
            lifo.extend(more_vertices.list_excluding(checked))
        return True

    def setup_order_search(self, v, w):
        """Traverse the topological order from order(v) to order(w)
           using a pointer from each end, meeting in middle.
           Along the way, populate the "rv" and "fw" deques.
           "rv" gets vertices reachable from vertex v.
           "fw" gets vertices reaching to vertex w.
           Set the midpoint for future use."""

        self.rv.clear()  # so the garbage collector doesn't have to ...
        self.rv.append(v)
        self.fw.clear()
        self.fw.append(w)

        right = self.topol.ord[w]
        left = self.topol.ord[v]
        while 1:
            left -= 1
            while left > right and \
                  not self.fwd(self.topol.ver[left], self.rv):
                left -= 1
            if self.fwd(self.topol.ver[left], self.rv):
                self.rv.append(self.topol.ver[left])
            if left == right:
                break
            right += 1
            while right < left and \
                  not self.rev(self.topol.ver[right], self.fw):
                right += 1
            if self.rev(self.topol.ver[right], self.fw):
                self.fw.append(self.topol.ver[right])
            if right == left:
                break
        self.mid = right  #  right == left at this (mid) point

    def update_topological_order(self, v, w):
        """Do cyclic permutation only from order(w) to order(v)."""

        mid = self.mid  # previously set via setup_order_search()
        ord_w = self.topol.ord[w]
        ord_v = self.topol.ord[v]

        # first clear out existing order info for all elements in rv and fw
        for c in self.rv, self.fw:
            self.topol.clear_orders(c)

        # now repopulate according to new ordering (cyclic permutation)
        left = mid
        while left >= ord_w:
            if self.topol.is_empty(left):
                self.topol.set_order(self.rv.popleft(), left)
            else:
                r = self.topol.ver[left]
                if self.fwd(r, self.rv):
                    self.rv.append(r)
                    self.topol.set_order(self.rv.popleft(), left)
            left -= 1
        right = mid + 1
        while right <= ord_v:
            if self.topol.is_empty(right):
                self.topol.set_order(self.fw.popleft(), right)
            else:
                r = self.topol.ver[right]
                if self.rev(r, self.fw):
                    self.fw.append(r)
                    self.topol.set_order(self.fw.popleft(), right)
            right += 1
        return True

    def fwd(self, v, vlist):
        """If edge exists from vertex v to any of vlist, return True"""
        for a in vlist:
            if self.adj[v][a]:
                return True
        return False

    def rev(self, v, vlist):
        """If edge exists from any of vlist to vertex v, return True"""
        for a in vlist:
            if self.adj[a][v]:
                return True
        return False

    def indegree(self, v):
        ret = 0
        for k in self.adj.data.keys():
            if self.adj[k][v]:
                ret += 1
        return ret

    def indegrees(self):
        ret = array('l', [0 for x in xrange(self.numv)])
        for k in self.adj.data.keys():
            for e in self.get_edgelist(k):
                ret[e] += 1
        return ret

    def complete_topological_sort(self):
        """For testing, not incremental - update order from scratch."""
        # modification of Kahn's algorithm:
        # decrement indegrees rather than delete edges
        ret = []
        indeg = self.indegrees()
        Q = [i for i, d in enumerate(indeg) if d == 0]
        while Q:
            n = Q.pop()
            ret.append(n)
            for m in self.get_edgelist(n):
                indeg[m] -= 1
                if not indeg[m]:
                    Q.append(m)
        self.topol.from_list(ret)
        return ret

    def vertex_count(self):
        return self.adj.v_count()

    def edge_count(self):
        return self.adj.e_count()

    def cycle_count(self):
        return self.cyc.e_count()

    def tprint(self):
        """Print graph as adjacency lists in topological order"""
        for v in self.topol.ver:
            if v == self.topol.no_val:
                continue
            print "%5d" % (v),
            print "->", self.get_edgelist(v)

    def mprint(self):
        """Print graph as adjacency lists from adjacency matrix"""
        lst = self.adj.data.keys()
        lst.sort()
        for v in lst:
            print "%5d" % (v),
            print "->", self.get_edgelist(v)

    def cprint(self):
        """Print previously detected cycles"""
        lst = self.cyc.data.keys()
        lst.sort()
        for v in lst:
            print "%5d" % (v),
            print "->", self.cyc.get_edgelist(v)

    def clone(self):
        g = TopoGraph(self.numv)
        g.adj = self.adj.clone()
        g.cyc = self.cyc.clone()
        g.topol = self.topol.clone()
        return g

    def from_adj_mat(self, adj_mat):
        if not isinstance(adj_mat, AdjacencyMatrix):
            return False
        self.adj = adj_mat.clone()
        self.numv = self.adj.numv
        self.cyc = AdjacencyMatrix(self.numv)
        self.topol = Orderer(self.numv)
        self.complete_topological_sort()

    def get_edgelist(self, v):
        return self.adj.get_edgelist(v)

    def oprint(self):
        self.topol.oprint()


class Orderer:
    """Stores vector order and inverse."""
    def __init__(self, num_vert):
        self.numv = num_vert
        self.no_val = -1
        self.ver = array('l', [self.no_val for x in xrange(self.numv)])
        self.ord = array('l', [self.no_val for x in xrange(self.numv)])
        self.next_empty = 0
        self.num_empty = self.numv

    def vertex_orders(self, v, w):
        """Add new vertices / return existing orders."""
        ord_w = self.ord[w]
        ord_v = self.ord[v]
        if ord_v == self.no_val:
            # no edge beginning or ending at v exists yet
            # so can insert v anywhere - first empty slot is fine
            ord_v = self.append(v)  # populates first empty slot
        if ord_w == self.no_val:
            # likewise if no edge beginning or ending at w exists yet
            ord_w = self.append(w)
        return (ord_v, ord_w)

    def set_order(self, v, o):
        """Maintain order and inverse arrays, update empty tracker."""
        self.ver[o] = v
        self.ord[v] = o
        if o == self.next_empty:
            self.num_empty -= 1
            self.update_next_empty(o)

    def clear_order(self, o):
        """Set empty slot for order and inverse, update empty tracker."""
        self.ord[self.ver[o]] = self.no_val
        self.ver[o] = self.no_val
        if o != self.next_empty:
             self.num_empty += 1
        if o < self.next_empty or self.next_empty == self.no_val:
            self.next_empty = o

    def clear_orders(self, collection):
        for element in collection:
            self.clear_order(self.ord[element])

    def append(self, v):
        """Place vertex in first empty slot."""
        if self.next_empty == self.no_val:
            return self.no_val  # XXX error
        o = self.next_empty
        self.set_order(v, o)
        return o

    def update_next_empty(self, start):
        #
        # note: testing with random graphs indicates that keeping track
        # of empties doesn't seem to add any significant performance
        # gain over just searching for next empty when needed ...
        # ie, if self.no_val in self.V: return self.V.index(self.no_val)
        #
        if self.num_empty == 0:
            return False
        for i in xrange(start, self.numv):
            if self.is_empty(i):
                break
        if i == self.numv:
             i = self.no_val
        self.next_empty = i
        return self.next_empty

    def is_empty(self, i):
        if self.ver[i] == self.no_val:
            return True
        return False

    def ocount(self):
        """Return count of ordered vertices."""
        return self.numv - self.ver.count(self.no_val)

    def oprint(self):
        print "order:",
        for i in self.ver:
            print i,
        print ""

    def from_list(self, lst):
        self.__init__(self.numv)
        i = 0
        for v in lst:
            self.set_order(v, i)
            i += 1

    def clone(self):
        o = Orderer(0)
        o.numv = self.numv
        o.ver.extend(self.ver)
        o.ord.extend(self.ord)
        o.next_empty = self.next_empty
        o.num_empty = self.num_empty
        return o


class AdjacencyMatrix:
    def __init__(self, num_vert):
        self.numv = num_vert
        self.data = {}

    def __getitem__(self, i):
        try:
            return self.data[i]
        except KeyError:
            self.data[i] = BitArray(self.numv)
            return self.data[i]

    def v_count(self):
        bits = BitArray(self.numv)
        for i, v in self.data.iteritems():
            if v.count_set_bits():
                bits[i] = 1
                bits.set_or(v)
        return bits.count_set_bits()

    def e_count(self):
        ret = 0
        for v in self.data.values():
            ret += v.count_set_bits()
        return ret

    def get_edgelist(self, v):
        try:
            return self.data[v].pos_list()
        except KeyError:
            return []

    def clone(self):
        m = AdjacencyMatrix(self.numv)
        for k in self.data.keys():
            m.data[k] = self.data[k].clone()
        return m


class BitArray:
    class Biterator:
        def __init__(self, bitarray):
            self.pos = 0
            self.bits = bitarray

        def __iter__(self):
            return self

        def next(self):
            if self.pos == self.bits.numbits:
                 raise StopIteration
            ret = self.bits[self.pos]
            self.pos += 1
            return ret

    def __init__(self, numbits):
        self.numbits = numbits
        self.first = self.numbits
        self.last = 0
        self.data = array('H')  # unsigned shorts
        self.chunksize = 8 * self.data.itemsize  # 16 bits expected
        self.numchunks = self.numbits / self.chunksize
        if (self.numchunks * self.chunksize) < self.numbits:
            self.numchunks += 1  # corner case ...
        self.data.fromlist([0 for x in xrange(0, self.numchunks)])

    def __iter__(self):
        return BitArray.Biterator(self)

    def __getitem__(self, i):
        return self.get(i)

    def __setitem__(self, i, val):
         self.set(i, val)

    def set(self, i, val):
        """Set bit at index i to value val."""
        if i < self.first:
            self.first = i
        if i > self.last:
            self.last = i
        if val:
            self.data[i/self.chunksize] |= (1 << (i%self.chunksize))
        else:
            mask = 0xFFFF ^ (1 << (i%self.chunksize))
            self.data[i/self.chunksize] &= mask

    def get(self, i):
        """Return value of bit at index i."""
        if self.data[i/self.chunksize] & (1 << (i%self.chunksize)):
            return 1
        return 0

    def pos_list(self):
        """Return list of indices of set bits."""
        # ... equivalent to:
        # return [i for i, v in enumerate(self) if v]
        # ... but an order of magnitude faster
        ret = []
        first_chunk = self.first / self.chunksize
        last_chunk = self.last / self.chunksize
        for i in xrange(first_chunk, last_chunk + 1):
            chunk = self.data[i]
            if chunk:
                 j = i * self.chunksize
                 while chunk:
                      if chunk & 1:
                           ret.append(j)
                      chunk = chunk >> 1
                      j += 1
        return ret

    def list_excluding(self, other):
        """Return list of indices of set bits not also set in other."""
        ret = []
        first_chunk = self.first / self.chunksize
        last_chunk = self.last / self.chunksize
        for i in xrange(first_chunk, last_chunk + 1):
            #
            # some room for more gratuitous optimization here
            # (could re-arrange loop to leverage other.first, etc.)
            # but good enough (do this all in C if speed necessary)
            #
            chunk = self.data[i] & (0xFFFF ^ other.data[i])
            if chunk:
                 j = i * self.chunksize
                 while chunk:
                      if chunk & 1:
                           ret.append(j)
                      chunk = chunk >> 1
                      j += 1
        return ret

    def count_set_bits(self):
        """Return number of "on" bits in array."""
        ret = 0
        first_chunk = self.first / self.chunksize
        last_chunk = self.last / self.chunksize
        if self.chunksize == 16:
            for i in xrange(first_chunk, last_chunk + 1):
                chunk = self.data[i]
                #
                # "parallel" count easy for 16-bit chunks ...
                #
                chunk = (chunk & 0x5555) + (chunk>>1 & 0x5555)
                chunk = (chunk & 0x3333) + (chunk>>2 & 0x3333)
                chunk = (chunk & 0x0f0f) + (chunk>>4 & 0x0f0f)
                chunk = (chunk & 0x00ff) + (chunk>>8 & 0x00ff)
                ret += chunk
        else:
            for i in xrange(first_chunk, last_chunk + 1):
                chunk = self.data[i]
                while chunk:
                    chunk &= chunk - 1
                    ret += 1
        return ret

    def set_or(self, other):
        for i in xrange(self.numchunks):
            self.data[i] |= other.data[i]

    def clone(self):
        b = BitArray(0)
        b.numbits = self.numbits
        b.first = self.first
        b.last = self.last
        b.data.extend(self.data)
        b.chunksize = self.chunksize
        b.numchunks = self.numchunks
        return b


class GraphTester:
    def __init__(self):
        self.g = None
        self.randomizer = random.Random()
        self.ri = self.randomizer.randint
        self.rs = self.randomizer.getstate()

    def simple_spec(self):
        """Imagine a graph that consists of directional links between
        nodes identified by small non-negative integers < 2**16. We
        define a "cycle" in the graph as a nonemp ty set of links that
        connect a node to itself.

Imagine an application that allows insertion of links, but wants to
prevent insertion of links that close cycles in the graph.

For example, starting from an empty graph, inserting links 1 -> 2 and 2
-> 3 would succeed; but inserting a third link 3 -> 1 would fail, since
it would close the cycle 1 -> 2 -> 3 -> 1. However, inserting a link 1
-> 3 instead would succeed."""
        self.g = TopoGraph(65536)
        insert_link = self.g.insert_link
        ret = insert_link(1, 2)
        if ret != "added":
           s = "failed insert_link(1, 2)" + ret
           return s
        print "added link 1 -> 2 ... ok"
        ret = insert_link(2, 3)
        if ret != "added":
           s = "failed insert_link(2, 3)" + ret
           return s
        print "added link 2 -> 3 ... ok"
        ret = insert_link(3, 1)
        if ret != "cycle":
           s = "failed cycle detection insert_link(3, 1)" + ret
           return s
        print "rejected link 3 -> 1 (cycle) ... ok"
        ret = insert_link(1, 3)
        if ret != "added":
           s = "failed insert_link(1, 3)" + ret
           return s
        print "added link 1 -> 3 ... ok"
        ret = insert_link(0, 65535)
        if ret != "added":
           s = "failed insert_link(0, 65535)" + ret
           return s
        print "added link 0 -> 65535 (non-negative, < 2^16) ... ok"
        ret = insert_link(1, 65536)
        if ret == "added":
           s = "failed out of bounds insert_link(1, 65536)" + ret
           return s
        print "rejected link 1 -> 65536 (65536 is not < 2^16) ... ok"
        ret = insert_link(-1, 0)
        if ret == "added":
           s = "failed out of bounds insert_link(-1, 0)" + ret
           return s
        print "rejected link -1 -> 0 (-1 not non-negative) ... ok"
        return "passed simple_spec()"

    def setup_randomizer(self, num_vert, rs=None):
        if rs != None:
            self.randomizer.setstate(rs)
        self.last_vertex = num_vert - 1

    def random_pair(self):
        v = self.randomizer.randint(0, self.last_vertex)
        w = self.randomizer.randint(0, self.last_vertex)
        while v == w:
            w = self.randomizer.randint(0, self.last_vertex)
        return (v, w)
               
    def edge_saturated_graph(self, num_vert, rs=None):
        g = TopoGraph(num_vert)
        self.setup_randomizer(num_vert, rs)
        max_edges = (num_vert - 1) * (num_vert / 2)
        i = 0
        while i < max_edges:
            v, w = self.random_pair()
            ret = g.insert_link(v, w)
            if ret == "added":
                i += 1
        return g
           
    def vertex_saturated_graph(self, num_vert, rs=None):
        g = TopoGraph(num_vert)
        self.setup_randomizer(num_vert, rs)
        i = 0
        while g.topol.ocount() < num_vert:
            v, w = self.random_pair()
            ret = g.insert_link(v, w)
            if ret == "added":
                i += 1
        return g
           
    def compare_with_dfs(self, num_vert):
        """Sanity check.  Return string with status details."""
        self.g = self.edge_saturated_graph(num_vert)
        print "comparing with dfs, wait a minute ..."
        ret = ""
        # run dfs cycle check on all edges in graph
        for k in self.g.adj.data.keys():
            for m in self.g.get_edgelist(k):
                if not self.g.dfs_acyclic(k, m):
                    print "dfs disagrees with edge", k, m
                    ret = "compare_with_dfs() failed edge"
        # now run dfs cycle check for previously disallowed cycles
        for k in self.g.cyc.data.keys():
            for m in self.g.cyc.get_edgelist(k):
                if self.g.dfs_acyclic(k, m):
                    print "dfs disagrees with cycle", k, m
                    ret = ret + "compare_with_dfs() failed cycle"
        if not ret:
            ret = "compare_with_dfs() passed: " \
                  + str(self.g.edge_count()) + " edges over " \
                  + str(self.g.vertex_count()) + " vertices"
        return ret

    def check_time(self, graph, mode="topological", rs=None):
        if rs != None:
            self.randomizer.setstate(rs)
        g = graph.clone()
        numv = g.numv
        max_edges = (numv - 1) * (numv / 2)
        last_test = int(max_edges * 0.9)
        total_edges = g.edge_count()
        total_cycles = g.cycle_count()
        print "initialized graph with", g.vertex_count(), "vertices",
        print "and", total_edges, "random edges"
        print "timing addition of %d random edges" \
              % (last_test - total_edges)
        print ""
        if mode == "topological":
            insert_link = g.insert_link
            print "using (faster) topological cycle check"
            print "expect generally constant/decreasing time: O(n^(5/2))"
            print "(with decreasing time to maintain topological order)"
        elif mode == "dfs":
            insert_link = g.insert_link_dfs
            print "using (slower) depth-first search cycle check"
            print "expect generally linear time: O(n + m)"
        print "number of vertices 'n' remains constant at %d" \
              % (numv)
        print "as number of edges 'm' increases from %d to %d" \
              % (total_edges, last_test)
        print ""
        total_time = 0.0
        t1 = time()
        edges = 0
        cycles = 0
        prev_i = 0
        i = 0
        while total_edges < last_test:
            v, w = self.random_pair()
            ret = insert_link(v, w)
            if ret == "added":
                edges += 1
                total_edges += 1
                i += 1
            elif ret == "cycle":
                cycles += 1
                i += 1
            if not i % 1000:
                if i > prev_i:
                    t2 = time()
                    prev_i = i
                    t = t2 - t1
                    total_time += t
                    total_cycles += cycles
                    print "%d edges added (%d total) " \
                          % (edges, total_edges),
                    print "%d cycles caught (%d total)  %.2f seconds" \
                          % (cycles, total_cycles, t)
                    edges = 0
                    cycles = 0
                    t1 = time()
        t2 = time()
        t = t2 - t1
        total_time += t
        print total_edges, "total edges added,",
        print "%d total cycles caught  %.2f seconds total time\n" \
              % (total_cycles, total_time)
        return g

    def prompt_yes(self, quest, dflt='y'):
        prompt = quest + " [y/n]" + " (" + dflt + ") "
        inp = ""
        while inp not in ('y', 'Y', 'n', 'M'):
            inp = raw_input(prompt)
            if inp == "":
                inp = dflt
        if inp == 'y' or inp == 'Y':
            return True
        return False
                   
    def prompt_int(self, quest="enter a number [integer]", dflt=0):
        prompt = quest + " (" + str(dflt) + ") "
        inp = ""
        while 1:
            inp = raw_input(prompt)
            if not inp:
                inp = dflt
            try:
                ret = int(inp)
                break
            except ValueError:
                continue
        return ret

    def prompt_filename(self, quest, dflt=""):
        if dflt:
            prompt = quest + " (\"" + dflt + "\") "
        else:
            prompt = quest
        inp = ""
        while not inp:
            inp = raw_input(prompt)
            if not inp:
                inp = dflt
        return inp


if __name__ == "__main__":
     gt = GraphTester()
     print gt.simple_spec()
     print "\n"
     if gt.prompt_yes('timing test next - continue?'):
         prompt = "enter number of vertices [positive integer]"
         num_vert = gt.prompt_int(prompt, 100)
         print "creating graph with %d vertices, may take a minute ..."\
               % (num_vert)
         if gt.prompt_yes("use saved randomizer?", "n"):
              fn = gt.prompt_filename("randomizer filename?",
                                      "topograph_randomizer")
              try:
                  fp = open(fn, 'rb')
                  gt.randomizer = pickle.load(fp)
                  fp.close()
              except IOError:
                  print "ERROR - couldn't open", fn
         initial_randomizer_state = gt.randomizer.getstate()
         g = gt.vertex_saturated_graph(num_vert)
         randomizer_state = gt.randomizer.getstate()
         gg = gt.check_time(g, "topological", randomizer_state)
         gg = gt.check_time(g, "dfs", randomizer_state)
         gg.complete_topological_sort()  # sort after adding via dfs
     print "\n"
     if gt.prompt_yes("print graph?"):
         gg.tprint()
     if gt.prompt_yes("save randomizer state?", "n"):
         # print initial_randomizer_state
         gt.randomizer.setstate(initial_randomizer_state)
         fn = gt.prompt_filename("randomizer filename?",
                                 "topograph_randomizer")
         try:
             fp = open(fn, "wb")
             pickle.dump(gt.randomizer, fp)
             fp.close()
         except IOError:
             print "SORRY - couldn't save randomizer file:", fn
             if gt.prompt_yes("print to screen?"):
                 print pickle.dumps(gt.randomizer)
